package other;

import java.util.*;

import org.junit.Test;

public class Ex146 {
    //错误，没有考虑到从中间取值的情况
    class LRUCacheX {
        private Queue<Integer> queue;
        private Map<Integer, Integer> map;
        private int capacity;
        public LRUCacheX(int capacity) {
            map = new HashMap<>();
            queue = new LinkedList<>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                queue.offer(queue.poll());
                return map.get(key);
            }
            else return -1;
        }
        
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                map.put(key, value);
                return;
            }
            if (queue.size() == capacity) {
                int k = queue.poll();
                map.remove(k); 
            } 
            map.put(key, value);
            queue.offer(key);
        }

        public String toString() {
            return queue.toString() + map.toString();
        }
    }
    @Test
    public void test() {
        LRUCache c = new LRUCache(3);
        c.put(1, 1);
        c.put(2, 2);
        c.put(3, 3);
        c.put(4, 4);
        System.out.println(c.get(4));
        System.out.println(c.get(3));
        System.out.println(c.get(2));
        System.out.println(c.get(1));
        c.put(5, 5);
        System.out.println(c.get(1));
        System.out.println(c.get(3));
        System.out.println(c.get(4));
        
    }

    /* 
        为什么非要双向链表：
        删除一个节点不仅与自身有关，还需要这个节点的指针
    */
    class LRUCache {

       public class DoubleList {
            Node head;
            Node tail;

           public class Node {
                Node pre;
                Node next;
                int key;
                int val;
                public Node (int key, int val) {
                    this.key = key;
                    this.val = val;
                }
            }

            public void addLast(int key, int val) {
                Node node = new Node(key, val);
                if (head == null) {
                    head = node;
                    tail = node;
                    return;
                }
                tail.next = node;
                node.pre = tail;
                tail = node;
            }

            public void addLast(Node node) {
                if (head == null) {
                    head = node;
                    tail = node;
                    return;
                }
                tail.next = node;
                node.pre = tail;
                tail = node;
            }

            public void addNodeToLast(Node node) {
                if (node.next == null) return;
                if (node == head) {
                    Node t = node;
                    head = head.next;
                    head.pre = null;
                    tail.next = t;
                    t.pre =tail;
                    tail = t;
                    return;
                }
                Node pre = node.pre;
                pre.next = node.next; //删除node
                tail.next = node;
                node.pre = tail;
                //移到最后
                tail = node;
            }

            public Node removeLast() {
                Node last = tail;
                tail = tail.pre;
                tail.next = null;
                return last;
            }

            public Node removeFirst() {
                if (head.next == null) {
                    Node t = head;
                    head = null;
                    tail = null;
                    return t;
                }
                Node first = head;
                head.next.pre = null;
                head = head.next;
                return first;
            }
        }
        private DoubleList list;
        private int capacity;
        private Map<Integer, DoubleList.Node> cache;
        public LRUCache(int capacity) {
            this.list = new DoubleList();
            this.capacity = capacity;
            this.cache = new HashMap<>();
        }
        
        public int get(int key) {
            if (!cache.containsKey(key)) return -1;
            DoubleList.Node node = cache.get(key);
            list.addNodeToLast(node);
            return node.val;
        }
        
        public void put(int key, int value) {
            DoubleList.Node node = list.new Node(key, value);
            if (cache.size() < capacity) {
                list.addLast(node);
                cache.put(key, node);
                return;
            }
            DoubleList.Node first = list.removeFirst();
            cache.remove(first.key);
            list.addLast(node);
            cache.put(key, node);
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
}